public class Array<E> {

    private E[] data;
    private int size;

    /**
     * 构造函数，传入数组的容量capacity并构造Array
     * @param capacity 数组的容量
     */
    public Array(int capacity) {
        //data = new E[capacity]; 这样写是不行的，Java不支持泛型数组，可以绕个弯子来写
        data = (E[]) new Object[capacity];
        size = 0;
    }

    /**
     * 无参构造函数，默认capacity = 10
     */
    public Array() {
        this(10);
    }

    public int getSize() {
        return size;
    }

    public int getCapacity() {
        return data.length;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 添加元素到数组末尾
     * @param element 要添加的元素
     */
    public void push(E element) {
        insert(size, element);
    }

    /**
     * add to the front
     * 添加元素到数组的头部
     * @param element 要添加的元素
     */
    public void unshift(E element) {
        insert(0, element);
    }

    /**
     * 向指定位置添加元素
     * @param index   第index个位置
     * @param element 要添加的元素
     */
    public void insert(int index, E element) {
        if (size == getCapacity()) {
            resize(2 * getCapacity());
        }
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Insert failed. Require index >= 0 and index > size");
        }
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        data[index] = element;
        size++;
    }

    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }

    /**
     * 通过索引删除某个元素
     * @param index 索引
     * @return 返回被删除的元素
     */
    public E splice(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Splice failed. Require index>=0 and index<=size");
        }
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }
        size--;
        data[size] = null; //这个语句可有可无
        if (size == data.length / 4 && data.length / 2 != 0) {
            resize(getCapacity() / 2);
        }
        return data[index];
    }

    /**
     * 删除数组末尾的元素
     * @return 返回被删除的末尾元素
     */
    public E pop() {
        return splice(size - 1);
    }

    /**
     * 删除数组最前面（头部）的元素
     * @return 返回被删除的头部元素
     */
    public E shift() {
        return splice(0);
    }

    /**
     * 删除某个元素
     * @param element 要删除的元素
     */
    public void remove(E element) {
        int index = indexOf(element);
        if (index != -1)
            splice(index);
    }

    /**
     * 找出某个元素在数组中的索引
     * @param element 要查找的元素
     * @return 如果找到该元素，则返回对应的index; 如果没有找到，则返回 -1
     */
    public int indexOf(E element) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(element)) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 访问index位置的元素
     * @param index 第index位置
     * @return 返回对应的元素
     */
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Get failed. Index is illegal.");
        }
        return data[index];
    }

    /**
     * 修改index位置的元素
     * @param index   第index位
     * @param element 修改后的元素
     */
    public void set(int index, E element) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Get failed. Index is illegal.");
        }
        data[index] = element;
    }

    /**
     * 查找数组是否有某个元素element
     * @param element 要查找的元素
     * @return true：包含该元素；false：不包含该元素
     */
    public boolean contains(E element) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(element)) {
                return true;
            }
        }
        return false;
    }

    @Override
    public String toString() {
        StringBuilder result = new StringBuilder();
        result.append(String.format("Array: size = %d, capacity = %d\n", size, getCapacity()));
        result.append('[');
        for (int i = 0; i < size; i++) {
            result.append(data[i]);
            if (i != size - 1) {
                result.append(", ");
            }
        }
        result.append(']');
        return result.toString();
    }
}
